import java.util.Iterator;
import java.util.Map;
import java.util.PriorityQueue;

public class HuffmanTree
{
    protected Node head;
    protected PriorityQueue<Node> PQ;
    public HuffmanTree(Map<Character, Integer> frequencyTable)
    {
        PQ = new PriorityQueue<Node>();
        Iterator it = frequencyTable.entrySet().iterator();

        //iterate through the pairs in the frequency table, making nodes out of them, and adding them to the PQ
        while (it.hasNext())
        {
            Map.Entry pairs = (Map.Entry)it.next();
            Node node = new Node((Character)pairs.getKey(), (Integer)pairs.getValue());
            PQ.add(node);
            it.remove();
        }
        this.makeTree();
    }

    public void makeTree()
    {
        while(!this.PQ.isEmpty())
        {
            if(this.PQ.size() > 1)
            {
                Node a = PQ.poll();
                Node b = PQ.poll();
                Node node = new Node(null,a.freq+b.freq);
                node.left = a;
                node.right = b;
                PQ.add(node);
            }
            else
            {
                this.head = PQ.poll();
            }
        }
    }

    public Map<Character, String> treeTraversal(Node current, String code, Map<Character, String> myMap)
    {
        if(current.left==(null) && current.right==(null))
        {
            myMap.put(current.character, code);
            //System.out.println(current.character + " " + code);
        }
        else
        {
            treeTraversal(current.left, code+"0", myMap);
            treeTraversal(current.right, code+"1", myMap);
        }
        return myMap;
    }

    public String decode(String input)
    {
        String output = "";
        Node currentNode = this.head;

        for(int i = 0; i < input.length(); i++)
        {
            Character current = input.charAt(i);
            if(currentNode.left == null && currentNode.right == null)
            {
                output += currentNode.character;
                currentNode = this.head;
            }
            else if(current == '0')
            {
                currentNode = currentNode.left;
                if(currentNode.left == null && currentNode.right == null)
                {
                    output += currentNode.character;
                    currentNode = this.head;
                }
            }
            else if(current == '1')
            {
                currentNode = currentNode.right;
                if(currentNode.left == null && currentNode.right == null)
                {
                    output += currentNode.character;
                    currentNode = this.head;
                }
            }
        }
        return output;
    }


    public class Node implements Comparable
    {
        protected Character character;
        protected Integer freq;
        protected Node left,right;

        public Node(Character myChar, Integer myFreq)
        {
            this.character = myChar;
            this.freq = myFreq;
        }

        @Override
        public int compareTo(Object o)
        {
            Node n = (Node)o;
            return this.freq - n.freq;
        }
    }
	
}
